Crossbar switches are widely used in computer and communications applications to connect a plurality of sources to a plurality of destinations. Since it is typically true that several sources may have outstanding requests for several destinations and many destinations may have multiple sources requesting access to them, some procedure must be implemented to assign sources to destinations during each switch cycle. Prior procedures have used various rules such as first-come-first-served, random assignment, and longest-queue-first (LQF) assignment in which an unmatched destination having the longest queue of requests is assigned to the as yet unmatched source requesting that destination also having the longest queue of outstanding requests. The first of these procedures suffers from the potential for “starvation”, a problem in which a request can be left pending for an unlimited period of time. The second procedure, while making indefinite starvation less likely, still puts no absolute bound on the length of time before a request is served. The third procedure can be advantageous when each source has a relatively large number of requests pending for each destination, since it attempts to minimize the maximum queue lengths and hence minimize the maximum latency through the switch, thereby also avoiding starvation.
However, if the system in which the crossbar switch is embedded is reasonably well balanced with the number of requests over a given period of time rarely exceeding the rate at which the system is able to service those requests, the queue lengths tend to remain relatively short most of the time, with the result that some sources frequently have no requests pending for some destinations. In fact, if this situation fails to obtain for any significant period of time, the queue lengths tend to grow without limit, resulting in generally unacceptable performance.
Under well-balanced conditions then, maximum latency is generally not the primary measure of interest because all requests can be serviced quickly if the switch is used efficiently; that is, if as many connections as possible are made during each switch cycle. When all sources are requesting access to all destinations, all procedures result in full switch utilization since, regardless of how sources and destinations are matched at any intermediate stage in the matching procedure, there must be at least one unmatched source requesting any unmatched destination. Note that, in a full-duplex system, which is assumed for purposes of the discussion here although in no way essential to it, the number of potential sources necessarily equals the number of potential destinations. If the number of sources and the number of destinations are not equal, maximum switch utilization is still achieved by any matching procedure as long as all sources have outstanding requests for all destinations. However, in this case either some sources or some destinations, depending on the direction of the imbalance, obviously will not be matched.
However, when not all sources are requesting access to all destinations, it is easy to see that the switch efficiency is highly dependent on the matching procedure. Consider, for example, the case in which four sources, arbitrarily named A, B, C and D, are requesting access to four destinations, 1 2, 3, 4, and assume that source A has one request pending for destination 1, that source B has one request for destination 1 and one request for destination 2, that source C has one request for destination 1, one request for destination 2 and one request for destination 3, and that source D has one request for each of the four destinations. Under the maximum queue-length procedure, destination 1 is matched first since it has the most pending requests. Further, since destination 1 is matched to the source requesting it that has the longest request queue, it is matched with source D. Similarly, under the same criterion, destination 2 is then matched with source C leaving destinations 3 and 4 with no remaining unassigned sources requesting access to them. Consequently, the switch is only 50% utilized. However, 100% utilization could have been achieved by matching destination 1 with source A, destination 2 with source B, destination 3 with source C and destination 4 with source D.
Therefore, there is a need for a method and apparatus that insures the highest level of switch utilization.